package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 133. 克隆图
 * @date 2025/5/28 20:25
 */
public class E133 {

    public static class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    private final HashMap<Node, Node> map = new HashMap<>();

    /**
     * 深度优先遍历，递归实现，有点类似于垃圾回收找root引用链
     *
     * @param node 节点
     * @return 克隆的节点
     */
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Node root = new Node(node.val);
        map.put(node, root);
        for (Node neighbor : node.neighbors) {
            if (!map.containsKey(neighbor)) {
                root.neighbors.add(cloneGraph(neighbor));
            } else {
                root.neighbors.add(map.get(neighbor));
            }
        }
        return root;
    }
}
